package twice.class_digui;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//全排列问题（无顺序）
public class Class03_PrintAllPermutations {
    public static List<String> permutation1(String s){
        char[] c = s.toCharArray();
        ArrayList<Character> ch = new ArrayList<>();
        for(char a : c){
            ch.add(a);
        }
        List<String> res = new LinkedList<>();
        String path = "";
        process(ch,path,res);
        return res;
    }
    public static void process(List<Character> ch,String path,List<String> res){
        if(ch.size() == 0){
            res.add(path);
        }else {
            //!!一定要在这写不要在if里面写
            int N = ch.size();
            for (int i = 0; i < N; i++) {
                char cur = ch.get(i);
                ch.remove(i);
                process(ch, path + cur, res);
                ch.add(i, cur);
            }
        }
    }

    public static List<String> permutation2(String s){
       List<String> ans = new LinkedList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        process1(str,0,ans);
        return ans;
    }
    static void process1(char[] str,int i,List<String> ans){
        if(i == str.length){
            ans.add(String.valueOf(str));
            return;}

        for (int j = i; j < str.length; j++) {
            swap(str,i,j);
            process1(str,i+1,ans);
            swap(str,i,j);
        }

    }
    //重复元素问题
    public static List<String> permutation3(String s){
                List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        process2(str, 0, ans);
        return ans;

//        List<String> ans = new LinkedList<>();
//        if (s == null || s.length() == 0) {
//            return ans;
//        }
//        char[] str = s.toCharArray();
//        process2(str,0,ans);
//        return ans;
    }
    static void process2(char[] str,int i,List<String> ans){

//        if (index == str.length) {
//            ans.add(String.valueOf(str));
//        } else {
//            boolean[] visited = new boolean[256];
//            for (int i = index; i < str.length; i++) {
//                if (!visited[str[i]]) {
//                    visited[str[i]] = true;
//                    swap(str, index, i);
//                    process2(str, index + 1, ans);
//                    swap(str, index, i);
//                }
//            }
//        }

        if (i == str.length) {
            ans.add(String.valueOf(str));
        } else {
            boolean[] visited = new boolean[256];
            for (int j = i; j < str.length; j++) {
                if (!visited[str[j]]) {
                    visited[str[j]] = true;
                    swap(str,i,j);
                    process2(str,i+1,ans);
                    swap(str,i,j);
                }
            }
        }
    }

//    public static void g2(char[] str, int index, List<String> ans) {
//        if (index == str.length) {
//            ans.add(String.valueOf(str));
//        } else {
//            boolean[] visited = new boolean[256];
//            for (int i = index; i < str.length; i++) {
//                if (!visited[str[i]]) {
//                    visited[str[i]] = true;
//                    swap(str, index, i);
//                    g2(str, index + 1, ans);
//                    swap(str, index, i);
//                }
//            }
//        }
//    }

    static void swap(char[] str,int i,int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    public static void main(String[] args) {
        String s = "acc";
        List<String> ans1 = permutation1(s);
        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans2 = permutation2(s);
        for (String str : ans2) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans3 = permutation3(s);
        for (String str : ans3) {
            System.out.println(str);
        }

    }

}
